/**
 * 广度优先搜索BFS
 * 广度优先搜索BFS类似于二叉树的层次遍历，基本思想是：
 * 先访问起始顶点v，接着由v出发，依次访问v的各个未被访问的邻接结点w1,w2,...,wn，继续同v一样的步骤
 * ，直到图中的所有结点都被访问为止。
 *
 * 广度优先算法要借助于队列数据结构来实现 
 * 
 * 迪杰斯特拉最短路径算法和普利姆最小生成树算法也运用了广度搜索算法的思想
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define VERTEX_NUM 20	//顶点最大个数

typedef enum{false, true} bool;

bool visited[VERTEX_NUM];//设置全局数组，用来记录各顶点是否被已访问

//使用链式线性表实现队列
typedef struct Queue{
	int data;
	struct Queue* next;
}Queue;

//定义邻接矩阵(存储各顶点之间的关系)
typedef struct{
	int adj;	//对于无权图，0表示不相邻，1表示相邻
	char* info; //弧或者边额外的信息
}ArcCell, AdjMatrix[VERTEX_NUM][VERTEX_NUM];

//定义图
typedef struct{
	int vex[VERTEX_NUM];	//存储各个顶点的数组,也称之为顶点索引数组
	AdjMatrix adjMatrix;	//二维数组，记录顶点与边之间的关系
	int vertex_num, arc_num;//vertex_num为图中顶点的个数, arc_num为图中边的个数
}MGraph;

//根据顶点寻找出该顶点在索引数组中下标
int Locate(MGraph* G, int vertex);

//创建无向图
void CreateDN(MGraph* G);

void visiteVex(MGraph* G, int vertex);

void BFS(MGraph* G);

/**
 * @brief 找出与x顶点的相邻元素
 * 
 * 求图G中顶点X的第一个邻接点，若有则返回顶点号,如果不存在则返回-1
 * 
 * @return 
 */
int FirstNeighbor(MGraph* G, int vertex);

/**
 * @brief 找出顶点v的下一个邻接点w
 * 
 * @return 返回的是找到的有关系结点的索引位置
 */
int NextNeighbor(MGraph* G, int v, int w);

//初始化队列
void InitQueue(Queue** Q);

//顶点入队列
void EnQueue(Queue** Q, int vertex);

//顶点出队列
void DeQueue(Queue** Q, int* vertex);

//判断队列是否为空
bool QueueIsEmpty(Queue* Q);

int main()
{
	
	return 0;
}

void CreateDN(MGraph* G)
{
	scanf("%d %d", &(G->vertex_num),&(G->arc_num));	//手动输入顶点数和边数
	for(int i=0;i<G->vertex_num;i++) scanf("%d",&(G->vex[i]));	//输入需要创建哪些结点
	
	//初始化各顶点之间边的关系，默认是各个顶点之间都不存在关系
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0;j<G->vertex_num;j++)
		{
			G->adjMatrix[i][j].adj=0;
			strcpy(G->adjMatrix[i][j].info, "");
		}
	}
	
	//确定各顶点之间边的关系
	for(int i=0;i<G->arc_num;i++)
	{
		int vertex1, vertex2;
		scanf("%d", &vertex1);
		scanf("%d", &vertex2);
		
		int locate_vertex1=Locate(G, vertex1);
		int locate_vertex2=Locate(G, vertex2);
		
		if(locate_vertex1==-1 || locate_vertex2==-1) return;
		
		//在二维数组确立关系(邻接矩阵是对称矩阵)
		G->adjMatrix[locate_vertex1][locate_vertex2].adj=1;
		G->adjMatrix[locate_vertex2][locate_vertex1].adj=1;
	}
}

int Locate(MGraph* G, int vertex)
{
	int i=0;
	for(; i<G->vertex_num; i++)
	{
		if(i==vertex) break;	//如果找到直接跳出循环
	}
	
	if(i>G->vertex_num) return -1;	//如果找不到就返回-1
	return i;
}


void BFS(MGraph* G)
{
	for(int i=0;i<G->vertex_num;i++) visited[i]=false;	//将每个顶点都设置为未访问
	//对于标记为未访问的结点调用广度优先搜索函数
	Queue* Q;
	InitQueue(&Q);
	
	for(int vertex=0; vertex<G->vertex_num; vertex++)
	{
		if(visited[vertex]==false)
		{
			//首先将该顶点设置为true，表示该顶点已被遍历
			visited[vertex]=true;
			//打印当前顶点在顶点索引数组中的索引
			visiteVex(G, vertex);
			EnQueue(&Q, G->vex[vertex]);
			
			while(!QueueIsEmpty(Q))
			{
				int elem;	//elem代表出队列的元素
				DeQueue(&Q, &elem);
				
				//获取顶点elem在索引数组中索引
				int elem_locate=Locate(G, elem);
				
				//w为有关联的顶点在索引数组中的索引(elem_locate等于函数FirstNeighbor中的vertex_index)
				for(int w=FirstNeighbor(G, elem_locate); w>=0; w=NextNeighbor(G, elem, w))
				{
					if(!visited[w])		//该顶点并没有被访问过
					{
						visited[w]=true;//设置该结点已被访问
						visiteVex(G,w); //输出该顶点
						EnQueue(&Q, G->vex[w]);//将该顶点入队列
					}
				}
				
			}
		}
	}
}


void InitQueue(Queue** Q)
{
	(*Q)=(Queue* )malloc(sizeof(Queue));
	(*Q)->next=NULL;
}

void EnQueue(Queue** Q, int vertex)
{
	Queue* elem=(Queue* )malloc(sizeof(Queue));
	elem->data=vertex;
	elem->next=NULL;
	Queue* tmp=(*Q);
	while(tmp->next) tmp=tmp->next;
	tmp->next=elem;
}

void DeQueue(Queue** Q, int* vertex)
{
	(*vertex)=(*Q)->next->data;
	Queue* delete_node=(*Q)->next;
	(*Q)->next=(*Q)->next->next;
	free(delete_node);
	delete_node=NULL;
}

bool QueueIsEmpty(Queue* Q)
{
	if(Q->next==NULL) return true;
	return false;
}

void visiteVex(MGraph* G, int vertex)
{
	printf("%d", G->vex[vertex]);
}


int FirstNeighbor(MGraph* G, int vertex_index)
{
	//按照行或者列找出和相邻的顶点的元素下标
	for(int i=0; i<G->vertex_num; i++)
	{
		if(G->adjMatrix[vertex_index][i].adj==1)
			return i;	// i就是与vertex第一个相邻顶点的索引位置
	}
	return -1;
	
}


int NextNeighbor(MGraph* G, int vertex_index, int w)
{
	//从前一个有关联的顶点的索引w的下一个位置开始继续访问，查找边关系为1的顶点，
	// 如果找到则返回该顶点的索引位置，否则返回-1
	for(int i=w+1; i<G->vertex_num; i++)
	{
		if(G->adjMatrix[vertex_index][i].adj==1) return i;	//仍然和寻找第一个相邻顶点函数一样，采用同样的行，即同样的vertex_index
	}
	return -1;
}